1. Field of the Invention
The present invention relates to a method for distributing a set of objects among a set of containers, for example, in an integrated circuit, and in particular relates to a method for improving the distribution of a set of circuits on a chip, balancing the load and/or fanout of a set of equivalent clock drivers in a clock tree, or placing data files on servers in a computer network.
2. Description of Related Art
Many integrated circuit design and other applications may be analogized as a set of objects, each of which is assigned to or placed in one of a set of containers. For example, in a clock optimization application on an integrated circuit, the containers may represent clock nets, with the objects representing clock sinks at specific locations on a chip. In a chip placement application, the containers may represent regions of a chip and the objects may represent circuits to be placed on the chip. In a network computing application, the containers may represent network server computers and the objects might represent large data files or databases residing on those servers.
In such an analog, one may assume that the application has the following characteristics:
Each object starts out assigned to an initial container, according to some set of criteria. In the clock optimization application an initial location-based sink clustering may define an initial set of clock nets. In the chip placement application an initial force-directed placement might be used to establish an initial placement. In the network workload optimization application, the initial assignment might place each file on the server closest to the file""s point of creation.
The containers have some spatial relationship with each other, i.e., each container X has a set of closest neighbor containers, each at some distance from X. In the clock optimization application the distance might be the rectilinear distance between the centroids (mean sink X and Y coordinates) of neighboring nets. In the chip placement application the distance might be the rectilinear distance between the centers of adjacent regions. In the network workload optimization application the distance might be inversely related to the channel capacity between adjacent servers.
Each container has some capacity and each object has a size, and the initial assignment of objects to containers may cause some containers to exceed their capacity, i.e., contain too many objects, and others may be underfilled, i.e., have too few objects. Alternatively, an objective of the object distribution may be to equalize the occupancy of all containers; this can be seen as equivalent to the capacity model by considering the capacity of each container to be the average occupancy of all containers. In the clock optimization application the objective might be to equalize the load (occupancy) of each clock net, and the size of each clock sink might be related to its input load. In the chip placement application the container capacity might be the amount of uncommitted area in the region represented by the container, and the size of the circuits to be placed might be the areas they occupy. In a network workload optimization application the server capacity might be the available processing power of the server and the file size might be related to the frequency of queries related to it and the computation required to respond to those queries. Alternatively, the server capacity might be related to the disk space available to store the files and the file size might be related to the disk space required to store the file.
There is some cost associated with moving an object from its initial container which increases rapidly with the distance that the object is moved. In the clock optimization application this might be because of the additional wire required to connect widely separated sinks. In the chip placement application, this might be because of the additional wire required to connect nets to a circuit which is moved from its xe2x80x9cidealxe2x80x9d location. In the network optimization application this might be the network bandwidth required to move the files.
A common approach to improving the distribution of objects between containers is to consider a pair or other small set of neighboring containers and to redistribute the objects between those containers so as to equalize the occupancy of each relative to its capacity. This is done repeatedly on all pairs or sets of neighboring clusters until convergence is achieved or some iteration limit is reached. This may require many iterations over all pairs of neighbors. One may consider the following list of numbers, representing the occupancy of a serially connected set of containers, and assume that the objective is to equalize the occupancy of all containers:
The iterative method described above might proceed as follows. Each of the following lines represents the state after the underlined pair of containers has been balanced. In each step it is assumed that the iterative algorithm always attacks the pair of neighbors with the largest occupancy difference, which are shown underlined:
Two observations can be made from this example. First, it takes a long time to converge. Second, it doesn""t actually converge to a completely balanced solution. The latter occurs because the granularity of objects prevents any local redistribution (since the final occupancy difference between all pairs of adjacent containers is one), even though a better global balance could be achieved by setting the occupancy of each container at 50.
Bearing in mind the problems and deficiencies of the prior art, it is therefore an object of the present invention to provide an improved method for distributing a set of objects on an integrated circuit.
It is another object of the present invention to provide a method for distributing a set of objects on an integrated circuit which converges more quickly than prior art methods.
A further object of the invention is to provide a method for distributing a set of objects on an integrated circuit which achieves better balance than prior art methods.
It is yet another object of the present invention to provide a method for distributing a set of objects on an integrated circuit which may be used for placement of a set of circuits on a chip, balancing the load and/or fanout of a set of equivalent clock drivers in a clock tree, or distributing large data files, e.g., databases, on network server computers.
Still other objects and advantages of the invention will in part be obvious and will in part be apparent from the specification.
The above and other objects and advantages, which will be apparent to one of skill in the art, are achieved in the present invention which is directed to, in a first aspect, a method of determining redistribution of objects among three or more containers in a network comprising determining an initial set of objects in each of the containers and identifying neighboring pairs of containers. The method then includes determining a cost of moving objects between each of the neighboring pairs of containers, determining a desired change in occupancy of each container, and subsequently determining a desired total size of a set of objects to be moved between each identified neighboring pair of containers by solving a set of simultaneous linear equations. The method may further include redistributing the objects among the neighboring pairs of containers in accordance with the solution of the set of simultaneous linear equations.
Preferably, the redistribution of objects among the neighboring pairs of containers comprises identifying neighboring pairs of containers in which the total size of objects to be moved does not exceed the total size of objects in the source container of the pair, moving objects between one of the identified pair of containers, and then repeating these steps until all neighboring pairs of containers have been identified. More preferably, the determination of redistribution of objects between each neighboring pair of containers includes rounding the total size of objects to be moved between neighboring pairs of containers determined by the solution of the set of simultaneous linear equations to the nearest whole number. After objects are moved between each container and a container in a neighboring pair, any error between the rounded whole number and the actual size of objects to be moved between neighboring pairs of containers determined by the solution of the set of simultaneous linear equations may be divided by the number of remaining neighbors of each container, and the quotient may be added to the total size of objects to be moved for each remaining neighbor. After objects are moved between each container and a container in a neighboring pair, a new set of simultaneous linear equations may be created and solved to determine the total size of objects to be moved between remaining neighboring pairs of containers.
The objects may be clock sinks and the containers clock nets on an integrated circuit chip, or the objects may be circuits to be placed in an integrated circuit and the containers regions of an integrated circuit chip, or the objects may be data files and the containers individual network server computers.
In another aspect, the present invention is directed to a method of determining redistribution of objects among three or more containers in a network comprising determining an initial set of objects in each of the containers, identifying neighboring pairs of containers, and determining a cost of moving objects between each of the neighboring pairs of containers. Thereafter, the method includes determining desired occupancy of each container after redistribution, and then subtracting the size of objects in each of the containers from the desired occupancy of each container after redistribution to determine the change in total size in each container. A theoretical electrical network model is then created by designating a plurality of nodes, each node representing a container, and designating a resistor between pair of nodes representing neighboring pairs of containers. Each resistor represents the cost of moving objects between the neighboring pairs of containers. The creation of the theoretical electrical network model further includes designating a current source connected to each node, with the current source representing the change in total size of objects in each container. The method then includes solving the theoretical electrical network model to determine theoretical current flow in each resistor, wherein the current flow in each resistor represents the total size of objects to be moved between neighboring pairs of containers. The method then includes determining redistribution of objects between each neighboring pair of containers in accordance with the theoretical current flow solved in the theoretical electrical network model. The method may further include redistributing the objects among the neighboring pairs of containers in accordance with the theoretical current flow solved in the theoretical electrical network model. Preferably, the theoretical electrical network model is solved by creating equations of current flow for each node, reducing the current flow equations for each node to simultaneous linear equations, and solving the simultaneous linear equations for theoretical current flow in each resistor.
The step of redistributing the objects among the neighboring pairs of containers may comprise initially, for each container, determining the total size of objects remaining in the container after all objects determined to be moved in accordance with the theoretical current flow solved in the theoretical electrical network model are moved to containers paired therewith. The step of redistributing the objects then includes identifying the container in the previous step having the largest total size of objects remaining in the container after all objects determined to be moved are moved to containers paired therewith. The objects from the container identified are then moved to a neighboring container to which the largest size of objects are to be moved from the container in accordance with the theoretical current flow solved in the theoretical electrical network model. Finally, these steps are repeated until all neighboring pairs of containers have been identified. Prior to the first step, there may be identified neighboring pairs of containers in which the total size of objects to be moved does not exceed the total size of objects in the source container of the pair.
Determining redistribution of objects between each neighboring pair of containers may include rounding the total size of objects to be moved between neighboring pairs of containers determined by the theoretical current flow to the nearest whole number. After objects are moved between each container and a container in a neighboring pair, any error between the rounded whole number and the actual size of objects to be moved between neighboring pairs of containers determined by the theoretical current flow may be divided by the total size of remaining neighbors of each container, and the quotient may be added to the total size of objects to be moved for each remaining neighbor. After objects are moved between each container and a container in a neighboring pair, a new theoretical electrical network model may be created and solved to determine the total size of objects to be moved between remaining neighboring pairs of containers.
The objects may be clock sinks and the containers clock nets on an integrated circuit chip, or the objects may be circuits to be placed in an integrated circuit and the containers regions of an integrated circuit chip, or the objects may be data files and the containers individual network server computers.